package tianhao.luo.recursion;

/**
 * 八皇后问题
 *
 * 在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即:任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
 * @author: tianhao.luo@hand-china.com 2021/6/17  17:21
 */
public class Queen8 {

    /**
     * max 表示有多少个皇后
     */
    private int max = 8;

    /**
     * 定义数组array,用来保存皇后的列的位置,数组的索引就表示皇后行的位置
     */
    int[] array = new int[max];


    /**
     * 总共的解法
     */
    private int count =0;


    public int getCount() {
        return count;
    }

    /**
     * 摆放皇后
     *
     * 特别注意:check是每一次递归时,进入到check中都有for (int i = 0; i < max; i++),因此会有回溯
     * @param n 第n个皇后
     */
    public void check(int n){
        // 1.判断是否已经走到了最大的第8列
        if (n == max){
            // 走完整个列,打印
            print();
            count++;
            return;
        }

        // 仅能摆放列的最大长度也为max;依次放入皇后,并判断是否冲突
        for (int i = 0; i < max; i++) {
            // 先把当前这个皇后n,放到该行的第i列,再判断它是否和前面摆放好的皇后冲突了
            array[n] = i;
            if (judgeConflict(n)){
                // 前面都没冲突,可以继续摆放皇后了
                check(n+1);
            }

            // 如果当前皇后和前面的冲突了,则又回到了 array[n] = i;
            // 此时i经过了++,表示将该皇后往后放一列,再进行判断是否进行冲突
        }
    }


    /**
     * 判断放置的该皇后n,是否和前面摆放好的冲突了
     * @param n 第n个皇后
     * @return 未冲突返回true
     */
    public boolean judgeConflict(int n){
        // 冲突的情况
        // 1.已有摆放好的皇后列和该皇后n的列相同
        // 2.已有摆放好的皇后和该皇后n位于对角线
        // 3.因为用数组的索引表示皇后的行,索引不会冲突,行也就不会冲突
        // 第n个皇后,表示已经摆放了n-1个皇后了,只能遍历n-1次
        for (int i = 0; i < n; i++) {
            // 1.数组的值表示列,array[i] == array[n],表示第i个皇后和第n个皇后的列冲突了
            // 2.判断两个元素是否位于对角线的逻辑: i和n的差,等于array[i]和array[n]的差
            // 具体判断逻辑可以参考docs目录下的,005-递归文档
            if (array[i] == array[n] || Math.abs(i-n) == Math.abs(array[i]-array[n])){
                return false;
            }
        }
        // 和前面的所有皇后都不冲突,则返回true
        return true;
    }


    /**
     * 打印
     */
    public void print(){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }

}
